home *** CD-ROM | disk | FTP | other *** search
/ 17 Bit Software 6: Level 6 / 17 Bit - Level 6 (1998)(Epic Marketing)[!].iso / quartz / q0429.dms / q0429.adf / libray / libobj / poly.c < prev    next >
C/C++ Source or Header  |  1992-05-20  |  8KB  |  344 lines
  1. /*
  2.  * poly.c
  3.  *
  4.  * Copyright (C) 1989, 1991, Craig E. Kolb
  5.  * All rights reserved.
  6.  *
  7.  * This software may be freely copied, modified, and redistributed
  8.  * provided that this copyright notice is preserved on all copies.
  9.  *
  10.  * You may not distribute this software, in whole or in part, as part of
  11.  * any commercial product without the express consent of the authors.
  12.  *
  13.  * There is no warranty or other guarantee of fitness of this software
  14.  * for any purpose.  It is provided solely "as is".
  15.  *
  16.  * $Id: poly.c,v 4.0.1.1 91/11/26 21:25:34 cek Exp Locker: cek $
  17.  *
  18.  * $Log:    poly.c,v $
  19.  * Revision 4.0.1.1  91/11/26  21:25:34  cek
  20.  * patch3: Additional check for degenerate polygon.
  21.  * 
  22.  * Revision 4.0  91/07/17  14:39:00  kolb
  23.  * Initial version.
  24.  * 
  25.  */
  26. #include "geom.h"
  27. #include "poly.h"
  28.  
  29. static Methods *iPolygonMethods = NULL;
  30. static char polyName[] = "polygon";
  31.  
  32. unsigned long PolyTests, PolyHits;
  33.  
  34. /*
  35.  * Create a reference to a polygon with vertices equal to those
  36.  * on the linked-list "plist."
  37.  */
  38. Polygon *
  39. PolygonCreate(plist, npoints, flipflag)
  40. PointList *plist;
  41. int npoints, flipflag;
  42. {
  43.     Polygon *poly;
  44.     Float indexval;
  45.     Vector *prev, *cur, anorm;
  46.     PointList *curp, *pltmp;
  47.     int i;
  48.  
  49.     if (npoints < 3) {
  50.         RLerror(RL_WARN, "Degenerate polygon.\n");
  51.         return (Polygon *)NULL;
  52.     }
  53.     
  54.     poly = (Polygon *)share_malloc(sizeof(Polygon));
  55.     /*
  56.      * Allocate space for the vertices.
  57.      */
  58.     poly->points = (Vector *)Malloc((unsigned)(npoints*sizeof(Vector)));
  59.     poly->npoints = npoints;
  60.  
  61.     /*
  62.      * Copy the vertices from the linked list to the array, freeing
  63.      * the linked list as we go so that the caller doesn't have
  64.      * to worry about doing so.
  65.      */
  66.     i = npoints -1;
  67.     for(curp = plist; curp != (PointList *)0; curp = pltmp) {
  68.         poly->points[i--] = curp->vec;
  69.         pltmp = curp->next;
  70.         free((voidstar)curp);
  71.     }
  72.  
  73.     /*
  74.      * Find normal to polygon.
  75.      */
  76.     poly->norm.x = poly->norm.y = poly->norm.z = 0.;
  77.     prev = &poly->points[poly->npoints -1];
  78.     for(i = 0,cur = poly->points;i < poly->npoints;i++, prev = cur, cur++) {
  79.         poly->norm.x += (prev->y - cur->y) * (prev->z + cur->z);
  80.         poly->norm.y += (prev->z - cur->z) * (prev->x + cur->x);
  81.         poly->norm.z += (prev->x - cur->x) * (prev->y + cur->y);
  82.     }
  83.  
  84.     if (VecNormalize(&poly->norm) == 0.) {
  85.         /*
  86.          * Degenerate normal --> degenerate polygon
  87.          */
  88.         RLerror(RL_WARN, "Degenerate polygon.\n");
  89.         free((voidstar)poly->points);
  90.         return (Polygon *)NULL;
  91.     }
  92.  
  93.     /*
  94.      * If filflag is true, flip the normal.
  95.      */
  96.     if (flipflag)
  97.         VecScale(-1, poly->norm, &poly->norm);
  98.  
  99.     /*
  100.      * Compute and store the plane constant.
  101.      */
  102.     poly->d = dotp(&poly->norm, &poly->points[0]);
  103.  
  104.     /*
  105.      * Find the "dominant" part of the normal vector.  This
  106.      * is used to turn the point-in-polygon test into a 2D problem.
  107.      */
  108.     anorm.x = fabs(poly->norm.x);
  109.     anorm.y = fabs(poly->norm.y);
  110.     anorm.z = fabs(poly->norm.z);
  111.     indexval = max(anorm.y, anorm.z);
  112.     indexval = max(anorm.x, indexval);
  113.  
  114.     if (indexval == anorm.x)
  115.         poly->index = XNORMAL;
  116.     else if (indexval == anorm.y)
  117.         poly->index = YNORMAL;
  118.     else
  119.         poly->index = ZNORMAL;
  120.  
  121.     return poly;
  122. }
  123.  
  124. Methods *
  125. PolygonMethods()
  126. {
  127.     if (iPolygonMethods == (Methods *)NULL) {
  128.         iPolygonMethods = MethodsCreate();
  129.         iPolygonMethods->create = (GeomCreateFunc *)PolygonCreate;
  130.         iPolygonMethods->methods = PolygonMethods;
  131.         iPolygonMethods->name = PolygonName;
  132.         iPolygonMethods->intersect = PolygonIntersect;
  133.         iPolygonMethods->normal = PolygonNormal;
  134.         iPolygonMethods->uv = PolygonUV;
  135.         iPolygonMethods->bounds = PolygonBounds;
  136.         iPolygonMethods->stats = PolygonStats;
  137.         iPolygonMethods->checkbounds = TRUE;
  138.         iPolygonMethods->closed = FALSE;
  139.     }
  140.     return iPolygonMethods;
  141. }
  142.  
  143. /*
  144.  * Quadrants are defined as:
  145.  *        |
  146.  *   1    |   0
  147.  *        |
  148.  * -------c--------
  149.  *        |
  150.  *   2    |   3
  151.  *        |
  152.  */
  153. #define quadrant(p, c) ((p.u<c.u) ? ((p.v<c.v) ? 2 : 1) : ((p.v<c.v) ? 3 : 0))
  154.  
  155. /*
  156.  * Perform ray-polygon intersection test.
  157.  */
  158. int
  159. PolygonIntersect(poly, ray, mindist, maxdist)
  160. Polygon *poly;
  161. Ray *ray;
  162. Float mindist, *maxdist;
  163. {
  164.     register int winding, i;
  165.     Vector dir, pos;
  166.     int quad, lastquad;
  167.     Float dist, left, right;
  168.     Vec2d center, cur, last;
  169.  
  170.     PolyTests++;
  171.     pos = ray->pos;
  172.     dir = ray->dir;
  173.     /*
  174.      * First, find where ray hits polygon plane, projecting
  175.      * along the polygon's dominant normal component.
  176.      */
  177.  
  178.     dist = dotp(&poly->norm, &dir);
  179.     if(fabs(dist) < EPSILON)
  180.         /*
  181.           * No intersection with polygon plane.
  182.          */
  183.         return FALSE;
  184.  
  185.     dist = (poly->d - dotp(&poly->norm, &pos)) / dist;
  186.     if(dist < mindist || dist > *maxdist)
  187.         /*
  188.          * Intersection point behind origin or too far.
  189.          */
  190.         return FALSE;
  191.  
  192.     /*
  193.      * Compute the point of intersection, projected appropriately.
  194.      */
  195.     if(poly->index == XNORMAL) {
  196.         center.u = pos.y + dist * dir.y;
  197.         center.v = pos.z + dist * dir.z;
  198.     } else if(poly->index == YNORMAL) {
  199.         center.v = pos.z + dist * dir.z;
  200.         center.u = pos.x + dist * dir.x;
  201.     } else  {
  202.         center.u = pos.x + dist * dir.x;
  203.         center.v = pos.y + dist * dir.y;
  204.     }    
  205.  
  206.     /*
  207.      * Is the point inside the polygon?
  208.      *
  209.      * Compute the winding number by finding the quadrant each
  210.      * polygon point lies in with respect to the the point in
  211.      * question, and computing a "delta" (winding number).  If we
  212.      * end up going around in a complete circle around
  213.      * the point (winding number is non-zero at the end), then
  214.      * we're inside.  Otherwise, the point is outside.
  215.      *
  216.      * Note that we can turn this into a 2D problem by projecting
  217.      * all the points along the axis defined by poly->index,
  218.      * the "dominant" part of the polygon's normal vector.
  219.      */
  220.     winding = 0;
  221.     VecProject(last, poly->points[poly->npoints -1], poly->index);
  222.     lastquad = quadrant(last, center);
  223.     for(i = 0; i < poly->npoints; i++, last = cur) {
  224.         VecProject(cur, poly->points[i], poly->index);
  225.         quad = quadrant(cur, center);
  226.         if (quad == lastquad)
  227.             continue;
  228.         if(((lastquad + 1) & 3) == quad)
  229.             winding++;
  230.         else if(((quad + 1) & 3) == lastquad)
  231.             winding--;
  232.         else {
  233.             /*
  234.              * Find where edge crosses
  235.              * center's X axis.
  236.              */
  237.             right = last.u - cur.u;
  238.             left = (last.v - cur.v) * (center.u - last.u);
  239.             if(left + last.v * right > right * center.v)
  240.                 winding += 2;
  241.             else
  242.                 winding -= 2;
  243.         }
  244.         lastquad = quad;
  245.     }
  246.  
  247.     if (winding != 0) {
  248.         *maxdist = dist;
  249.         PolyHits++;
  250.         return TRUE;
  251.     }
  252.     return FALSE;
  253. }
  254.  
  255. /*
  256.  * Return the normal to the polygon surface.
  257.  */
  258. /*ARGSUSED*/
  259. int
  260. PolygonNormal(poly, pos, nrm, gnrm)
  261. Polygon *poly;
  262. Vector *pos, *nrm, *gnrm;
  263. {
  264.     *gnrm = *nrm = poly->norm;
  265.     return FALSE;
  266. }
  267.  
  268. /*ARGSUSED*/
  269. void
  270. PolygonUV(poly, pos, norm, uv, dpdu, dpdv)
  271. Polygon *poly;
  272. Vector *pos, *norm, *dpdu, *dpdv;
  273. Vec2d *uv;
  274. {
  275.     /*
  276.      * Since there's no nice way to do this, we wimp out and
  277.      * do the following...
  278.      *
  279.      * Of course, we could force the user to specify U and V
  280.      * axes, but forcing them to use X and Y as U and V is
  281.      * just as arbitrary and much simpler to deal with.
  282.      */
  283.     uv->u = pos->x;
  284.     uv->v = pos->y;
  285.     if (dpdu) {
  286.         dpdu->x = 1.;
  287.         dpdu->y = dpdu->z = 0.;
  288.         dpdv->x = dpdv->z = 0.;
  289.         dpdv->y = 1.;
  290.     }
  291. }
  292.  
  293. /*
  294.  * Compute the extent of a polygon
  295.  */
  296. void
  297. PolygonBounds(poly, bounds)
  298. Polygon *poly;
  299. Float bounds[2][3];
  300. {
  301.     register int i;
  302.  
  303.     bounds[LOW][X] = bounds[HIGH][X] = poly->points[0].x;
  304.     bounds[LOW][Y] = bounds[HIGH][Y] = poly->points[0].y;
  305.     bounds[LOW][Z] = bounds[HIGH][Z] = poly->points[0].z;
  306.  
  307.     for (i = 1 ;i < poly->npoints; i++) {
  308.         if (poly->points[i].x < bounds[LOW][X])
  309.             bounds[LOW][X] = poly->points[i].x;
  310.         if (poly->points[i].x > bounds[HIGH][X])
  311.             bounds[HIGH][X] = poly->points[i].x;
  312.         if (poly->points[i].y < bounds[LOW][Y])
  313.             bounds[LOW][Y] = poly->points[i].y;
  314.         if (poly->points[i].y > bounds[HIGH][Y])
  315.             bounds[HIGH][Y] = poly->points[i].y;
  316.         if (poly->points[i].z < bounds[LOW][Z])
  317.             bounds[LOW][Z] = poly->points[i].z;
  318.         if (poly->points[i].z > bounds[HIGH][Z])
  319.             bounds[HIGH][Z] = poly->points[i].z;
  320.     }
  321. }
  322.  
  323. char *
  324. PolygonName()
  325. {
  326.     return polyName;
  327. }
  328.  
  329. void
  330. PolygonStats(tests, hits)
  331. unsigned long *tests, *hits;
  332. {
  333.     *tests = PolyTests;
  334.     *hits = PolyHits;
  335. }
  336.  
  337. void
  338. PolygonMethodRegister(meth)
  339. UserMethodType meth;
  340. {
  341.     if (iPolygonMethods)
  342.         iPolygonMethods->user = meth;
  343. }
  344.